package gold.digger;

import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.*;
import java.util.Random;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC473 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution_Simulated_Annealing {
        int ms[];
        int n, k;
        Random random = new Random(20220601);
        boolean ans = false;
        double hi = 1e4, lo = 1e-4, fa = 0.98;
        int N = 400;

        int calc() {
            int diff = 0;
            for (int i = 0, j = 0; i < 4; i++) {
                int cnt = 0;
                while (j < n && cnt < k) cnt += ms[j++];
                diff += Math.abs(cnt - k);
            }
            if (diff == 0) ans = true;
            return diff;
        }

        void sa() {
            for (double t = hi; t > lo && !ans; t *= fa) {
                int a = random.nextInt(n), b = random.nextInt(n);
                int prev = calc();
                swap(ms, a, b);
                int cur = calc();
                int diff = prev - cur;
                if (Math.log(diff / t) > random.nextDouble()) swap(ms, a, b);
            }
        }

        public boolean makesquare(int[] _ms) {
            ms = _ms;
            n = ms.length;
            int sum = 0;
            for (int i : ms) sum += i;
            k = sum / 4;
            if (k * 4 != sum) return false;
            shuffle(ms);
            while (N-- > 0) sa();
            return ans;
        }

        void shuffle(int[] arr) {
            for (int i = n; i > 0; i--) {
                int idx = random.nextInt(i);
                swap(arr, idx, i - 1);
            }
        }

        void swap(int[] arr, int i, int j) {
            int c = arr[i];
            arr[i] = arr[j];
            arr[j] = c;
        }
    }

    class Solution {
        public boolean makesquare(int[] nums) {
            if (null == nums || nums.length < 4) return false;

            int sum = 0;
            for (int num : nums) sum += num;

            if (sum % 4 != 0) return false;
            int partSum = sum / 4;

            int[] groupSum = new int[4];
            return dfs(nums, groupSum, 0, partSum);
        }

        public boolean dfs(int[] nums, int[] groupSum, int curPos, int partSum) {
            if (curPos >= nums.length) return isMatch(groupSum, partSum);
            for (int j = 0; j < 4; j++) {
                if (groupSum[j] + nums[curPos] <= partSum) {
                    groupSum[j] += nums[curPos];
                    if (dfs(nums, groupSum, curPos + 1, partSum)) return true;
                    groupSum[j] -= nums[curPos];
                }
            }

            return false;
        }

        public boolean isMatch(int[] groupSum, int partSum) {
            for (int sum : groupSum) {
                if (sum != partSum) return false;
            }
            return true;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[5,5,5,5,4,4,4,4,3,3,3,3]");
        int[] arr1 = InputUtil.toIntegerArray("[20,13,19,19,4,15,10,5,5,15,14,11,3,20,11]");

        System.out.println(solution.makesquare(arr1));
    }

    public static void main(String[] args) throws Exception {
        LC473 an = new LC473();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
